﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>


struct TreeNode {
    int val;
      struct TreeNode *left;
      struct TreeNode *right;
};

//二叉树的前序遍历
//https://leetcode.cn/problems/binary-tree-preorder-traversal/description/
typedef struct TreeNode BTNode;

int BinaryTreeSize(BTNode* root)
{
    if (root == NULL)
    {
        return 0;
    }

    return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

void preord(BTNode* root, int* arr, int*i)
{
    if (root == NULL)
    {
        return;
    }
    arr[(*i)++] = root->val;

    preord(root->left, arr, i);
    preord(root->right, arr,i);

}


int* preorderTraversal(struct TreeNode* root, int* returnSize) {

    int size = BinaryTreeSize(root);
    *returnSize = size;
    int* arr = (int*)malloc(size * sizeof(int));
    int i = 0;
    preord(root, arr, &i);
    return arr;
}


//二叉树的中序遍历
//https://leetcode.cn/problems/binary-tree-inorder-traversal/description/
typedef struct TreeNode BTNode;

int BinaryTreeSize(BTNode* root)
{
    if (root == NULL)
    {
        return 0;
    }

    return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

void inorder(BTNode* root, int* arr, int* i)
{
    if (root == NULL)
    {
        return;
    }
    inorder(root->left, arr, i);
    arr[(*i)++] = root->val;
    inorder(root->right, arr, i);

}


int* inorderTraversal(struct TreeNode* root, int* returnSize) {

    int size = BinaryTreeSize(root);
    *returnSize = size;
    int* arr = (int*)malloc(size * sizeof(int));
    int i = 0;
    inorder(root, arr, &i);
    return arr;
}

//二叉树的后序遍历
//https://leetcode.cn/problems/binary-tree-postorder-traversal/description/

typedef struct TreeNode BTNode;
int BinaryTreeSize(BTNode* root)
{
    if (root == NULL)
    {
        return 0;
    }

    return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

void postorder(BTNode* root, int* arr, int* i)
{
    if (root == NULL)
    {
        return;
    }
    postorder(root->left, arr, i);
    postorder(root->right, arr, i);
    arr[(*i)++] = root->val;

}


int* postorderTraversal(struct TreeNode* root, int* returnSize) {

    int size = BinaryTreeSize(root);
    *returnSize = size;
    int* arr = (int*)malloc(size * sizeof(int));
    int i = 0;
    postorder(root, arr, &i);
    return arr;
}

//单值二叉树

//https://leetcode.cn/problems/univalued-binary-tree/

typedef struct TreeNode BTNode;

bool isUnivalTree(struct TreeNode* root) {
    if (root == NULL)
    {
        return true;
    }
    
    if (root->left && (root->val != root->left->val))
    {
   
        return false;
    }
    if (root->right&&(root->val != root->right->val))
    {
        return false;
    }
    return  isUnivalTree(root->left) && isUnivalTree(root->right);
}


//相同的树
//https://leetcode.cn/problems/same-tree/description/


typedef struct TreeNode BTNode;

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {

    if (p == NULL && q == NULL)
    {
        return true;
    }

    if (!(p != NULL && q != NULL))
    {
        return false;
    }

    if (p != NULL && q!= NULL)
    {
        if (p->val != q->val)
        {
            return false;
        }
    }
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}


//另一棵树的子树
//https://leetcode.cn/problems/subtree-of-another-tree/


typedef struct TreeNode BTNode;

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {

    if (p == NULL && q == NULL)
    {
        return true;
    }

    if (!(p != NULL && q != NULL))
    {
        return false;
    }

    if (p != NULL && q != NULL)
    {
        if (p->val != q->val)
        {
            return false;
        }
    }
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}


bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
    
    if (root == NULL && subRoot != NULL)
    {
        return false;
    }

    if (root == NULL && subRoot == NULL)
    {
        return true;
    }

    
    if (isSameTree(root, subRoot))
    {
        return true;
    }
    return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);

}

//对称二叉树
//https://leetcode.cn/problems/symmetric-tree/description/
typedef struct TreeNode BTNode;

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {

    if (p == NULL && q == NULL)
    {
        return true;
    }

    if (!(p != NULL && q != NULL))
    {
        return false;
    }

    if (p != NULL && q != NULL)
    {
        if (p->val != q->val)
        {
            return false;
        }
    }
    return isSameTree(p->left, q->right) && isSameTree(p->right, q->left);
}

bool isSymmetric(struct TreeNode* root) {
    
    if (root == NULL)
    {
        return true;
    }
   
    return isSameTree(root->left, root->right);
}
